package labuladong;

import java.util.Arrays;

public class CountPrimes {

    //  CKG TODO 2023/6/3: 返回的是　２到ｎ里面所有的素数 左闭右开的区间
    public  int countPrimes(int n){
        int count=0;

        for (int i = 2; i < n; i++) {
            if (isPrime(i)){
                count++;
            }
        }

        return count;
    }

    public  boolean  isPrime(int n){
        for (int i = 2; i*i <=n ; i+=1) {
            if (n%i==0){
                return false;
            }
        }
        return  true;
    }

    public int countPrimes1(int n){
        int count=0;
        boolean[]  isPrime= new boolean[n];
        //  CKG TODO 2023/6/3: 利用坐标筛选数字　　
        Arrays.fill(isPrime,true);
        for (int i = 2; i <n ; i++) {
            if (isPrime[i]){
                for (int j =2*i; j <n; j+=i) {
                    isPrime[j]=false;

                }
            }
        }

        for (int i = 2; i <n ; i++) {
            if (isPrime[i]){
                count++;
            }

        }





        return count;

    }






    public static void main(String[] args) {
        CountPrimes countPrimes = new CountPrimes();
        System.out.println(countPrimes.countPrimes1(10));
    }

}
